11.4. Çırpı Fonksiyonu (Hash Function)

Çırpı fonksiyonu arama işlemini bir çırpıda yapmak ve aranana doğrudan ulaşmak için kullanılan bir fonksiyondur. Fonksiyona, arama işleminde kullanılacak anahtar sözcük değeri girilir ve karşılığında bir tamsayı alınır. Bu tamsayı, indis gibi kullanılarak dizi düzeninde tutulan veriye erişmek için kullanılır. Veriler üzerinde arama yapmak için en hızlı yöntem çırpı fonksiyonu kullanılmasıdır denilebilir; idealde, arama işlemi bir çırpıda yapıldığı için arama karmaşıklığı olur. Ancak, uygulamada, çoğu zaman için ideal çırpı fonksiyonunu bulmak mümkün değildir.

Çırpı algoritması uygulamalarında üzerinde en çok uğraşılan konulardan birisi çatışmaların giderilmesi üzerine olmaktadır. [ÇÖLKESEN ve ALİEFENDİOĞLU-1984] [GONNET-1984]

Çırpı algortimasının bileşenleri ve bunların işlevleri

Çırpı algoritmasının fonksiyonel açıdan donanım karşılığı RAM, ROM gibi belleğe ek olarak asosiyatif bellek kullanılmasıdır. Asosiyatif bellek veya diğer bir deyişle içeriğiyle erişilebilen bellek (CAM), verinin bir kısmıyla tamamına erişme imkanı veren bir bellek mimarisine sahiptir. Bir bellek gözü için gerekli maliyet RAM, ROM gibi bellek türlerine göre fazla olduğundan dolayı özel bilgisayarlarda veya bazı özel birimlerde kullanılmaktadır. Daha fazla bilgi için bkz [ARSAN ve ÇÖLKESEN-2001]